package Numpy;

/**
 * 示例 1: 给定 nums = [3,2,2,3], val = 3,
 * 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
 * 你不需要考虑数组中超出新长度后面的元素。
 */
public class ArrayRemoveElement {
    public static void main(String[] args) {
        System.out.println(removeElement3(new int[]{3,2,2,3,4,5,3}, 3));
    }
    // 暴力解法 第一个循环找出等于val的值，第二个循环数组元素前移覆盖，整体的数组长度减去1
    public static int removeElement1(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < nums.length; j++) {
                    nums[j-1] = nums[j];
                }
                size--;
                i--;
            }

        }
        return size;
    }

    // 双指针法 第一个指针保存不等于val值的序列，第二个指针将不等于val的值往前移动给第一个指针保存。
    public static int removeElement2(int[] nums, int val) {
        int size = nums.length;
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < size; fastIndex++) {
            if(val != nums[fastIndex]){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }

    // 类似于一轮快排 将后面不等于val的值，覆盖前面等于val的值，在数组可变的题目中可行
    public static int removeElement3(int[] nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                int temp = nums[leftIndex];
                nums[leftIndex] = nums[rightIndex];
                nums[rightIndex] = temp;
                leftIndex++;
                rightIndex--;
            }
        }
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素
    }
}
